package lc;

import java.util.ArrayList;

public class PascalsTriangle {

    public ArrayList<ArrayList<Integer>> generate(int numRows) {
    	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    	if (numRows < 1) {
    		return result;
    	}
    	else if (numRows == 1) {
    		ArrayList<Integer> list = new ArrayList<Integer>();
    		list.add(1);
    		result.add(list);
    		return result;
    	}
    	else {
    		ArrayList<ArrayList<Integer>> sub = generate(numRows-1);
    		result.addAll(sub);
    		int last = sub.size()-1;
    		ArrayList<Integer> pre = sub.get(last);
    		ArrayList<Integer> list = new ArrayList<Integer>();
    		list.add(1);
    		for (int i=0; i<pre.size()-1; i++) {
    			list.add(pre.get(i)+pre.get(i+1));
    		}
    		list.add(1);
    		result.add(list);
    		return result;
    	}
    }        

    public static void main(String ...strings) {
    	PascalsTriangle sol = new PascalsTriangle();
    	ArrayList<ArrayList<Integer>> generate = sol.generate(5);
    	System.out.println(generate);
    }
}
